package com.fw.leetcode.tree;

import com.fw.leetcode.LeetCode;

/**
 * 100. Same Tree
 *
 * Given the roots of two binary trees p and q, write a function to check if they are the same or not.
 * Two binary trees are considered the same if they are structurally identical, and the nodes have the same value.
 *
 * Example 1:
 *         1            1
 *      2     3      2     3
 *
 *  Input: p = [1,2,3], q = [1,2,3]
 *  Output: true
 *
 * Example 2:
 *  Input: p = [1,2], q = [1,null,2]
 *  Output: false
 *
 * Example 3:
 *  Input: p = [1,2,1], q = [1,1,2]
 *  Output: false
 *
 * Constraints:
 *  The number of nodes in both trees is in the range [0, 100].
 *  -10^4 <= Node.val <= 10^4
 */
public class Num_0100 implements LeetCode {
    private interface Solution extends Tree {
        boolean isSameTree(TreeNode p, TreeNode q);

        default void assertExpected(Integer[] root1, Integer[] root2, boolean expected) {
            TreeNode rooNode1 = buildBinaryTree(root1);
            TreeNode rooNode2 = buildBinaryTree(root2);
            if (isSameTree(rooNode1, rooNode2) != expected) {
                isSameTree(rooNode1, rooNode2);
            }
        }
    }

    private static class MySolution implements Solution {

        @Override
        public boolean isSameTree(TreeNode p, TreeNode q) { // 深度优先遍历（递归）：时O(n) 空O(log n)
            if (p == null && q == null) {
                return true;
            }
            if (p != null && q != null && p.val == q.val) {
                return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
            }
            return false;
        }
    }

    public static void main(String[] args) {
        Solution solution = new MySolution();
        solution.assertExpected(new Integer[]{1,2,3}, new Integer[]{1,2,3}, true);
        solution.assertExpected(new Integer[]{1,2}, new Integer[]{1,null,2}, false);
        solution.assertExpected(new Integer[]{1,2,1}, new Integer[]{1,1,2}, false);
    }
}
